package queue

import (
	"sync/atomic"
	"unsafe"
)

// node 队列中的元素结点
type node struct {
	Next  unsafe.Pointer
	Value any
}

// LinkedQueue 基于链表实现的无锁队列
type LinkedQueue struct {
	head  unsafe.Pointer
	tail  unsafe.Pointer
	count atomic.Int32
}

func NewLinkedQueue() *LinkedQueue {
	node := &node{
		Next:  nil,
		Value: nil,
	}

	return &LinkedQueue{
		head: unsafe.Pointer(node),
		tail: unsafe.Pointer(node),
	}
}

func (q *LinkedQueue) Poll() any {
	for {
		// 获取头结点和尾节点，以及需要出列的结点
		tail := load(&q.tail)
		head := load(&q.head)
		next := load(&head.Next)

		// 确保当前 head 和队列中的 head 还是一样，即还没有其它
		// 协程弹出节点
		if head == load(&q.head) {
			// 空队列的情况
			if head == tail {
				// 空队列直接返回 nil
				if next == nil {
					return nil
				}
				// next != nil 即代表有插入的情况在另一个协程发生了，
				// 所以需要更新一下尾部的结点，不需要确保更新成功，
				// 然后进行下一次循环，获取最新的头尾结点
				cas(&q.tail, tail, next)
			} else {
				// 不是空队列，将 next 中的值提出，然后释放掉 value 的内存空间
				cur := next.Value
				next.Value = nil
				// 将 head 尝试更新成 next，因为出列了一个节点，自然要往后挪，
				// 如果失败了，就需要重新循环获取最新值，因为有其它协程已经弹出了
				// 这个节点
				if cas(&q.head, head, next) {
					q.count.Add(-1)
					return cur
				}
			}
		}
	}
}

func (q *LinkedQueue) Offer(v any) {
	node := &node{
		Next:  nil,
		Value: v,
	}

	// cas 不能确保一次成功，所以要轮询获得最新的 tail
	for {
		tail := load(&q.tail)
		next := load(&tail.Next)

		if tail == load(&q.tail) {
			if next == nil {
				if cas(&tail.Next, next, node) {
					cas(&q.tail, tail, node)
					q.count.Add(1)
					return
				}
			} else {
				// next != nil 即表示有节点已经入队，需要更新尾部，
				// 不需要确认更新是否成功，因为其它协程也会进行这一步，
				// 几次 for 循环之后就会更新掉，这个插入过程就能获得
				// 到最新的尾部了
				cas(&q.tail, tail, next)
			}
		}
	}
}

func (q *LinkedQueue) Count() int32 {
	return q.count.Load()
}

// load 加载指针的值
func load(p *unsafe.Pointer) *node {
	return (*node)(atomic.LoadPointer(p))
}

// cas go cas 实现
func cas(p *unsafe.Pointer, old, new *node) bool {
	return atomic.CompareAndSwapPointer(p, unsafe.Pointer(old), unsafe.Pointer(new))
}
